/**
 * 第i个人扣除n所花费的时间为:
 * workerTimes[i] * (1 + 2 + ... + n)
 * 现在一共要扣除 mountainHeight
 * 所有人可以同时工作，问最少需要多少时间
 * 
 * 二分，给定时间T，可以计算出每个人在T时间内扣除的数量
 * 加起来看是否大于等于 mountainHeight
 * 
 * 右边界要设大一点，但1<<62肯定会超范围
 * 
 */
class Solution {

using llt = long long;


public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        llt left = 1, right = 1LL << 58, mid;
        do{
            mid = (left + right) >> 1;
            if(not check(mid, mountainHeight, workerTimes)) left = mid + 1;
            else right = mid - 1;
        }while(left <= right);
        return left;
    }

    bool check(llt limit, int mountainHeight, vector<int>& workerTimes){
        for(auto i : workerTimes){
            llt tmp = limit / i;
            llt d = 1 + 8 * tmp;
            llt t = (-1 + sqrt(d)) / 2;
            mountainHeight -= t;
            if(mountainHeight <= 0) return true;
        }
        return false;
    }
};